#define _CRT_SECURE_NO_WARNINGS 1

//#include<string.h>
//#include<assert.h>
//#include<iostream>
//
//using namespace std;
//
//namespace yyh
//{
//	class string
//	{
//	public:
//		string(const char* str = "")
//		{
//			assert(str);
//			_str = new char[strlen(str) + 1];
//			strcpy(_str, str);
//		}
//
//		string(const string& s)
//			:_str(new char[strlen(s._str) + 1])
//		{
//			strcpy(_str, s._str);
//		}
//
//		string& operator =(const string& s)
//		{
//			if (this != &s)
//			{
//				delete[] _str;
//				_str = new char[strlen(s._str) + 1];
//				strcpy(_str, s._str);
//			}
//			return *this;
//		}
//
//		~string()
//		{
//			delete[] _str;
//			_str = nullptr;	
//		}
//
//	private:
//		char* _str;
//	};
//
//	void test()
//	{
//		string s1;
//
//		string s2("hello world");
//
//		string s3(s2);
//
//		s1 = s3;
//	}
//}


//#include<stdlib.h>
//#include<stdio.h>
//
//void _MergeSort(int* arr, int left, int right, int* temp)
//{
//    if (left >= right)
//    {
//        return;
//    }
//    int mid = (left + right) / 2;
//    _MergeSort(arr, left, mid, temp);
//    _MergeSort(arr, mid + 1, right, temp);
//    int begin1 = left, end1 = mid;
//    int begin2 = mid + 1, end2 = right;
//    int index = left;
//    while (begin1 <= end1 && begin2 <= end2)
//    {
//        if (arr[begin1] < arr[begin2])
//        {
//            temp[index++] = arr[begin1++];
//        }
//        else
//        {
//            temp[index++] = arr[begin2++];
//        }
//    }
//    while (begin1 <= end1)
//    {
//        temp[index++] = arr[begin1++];
//    }
//    while (begin2 <= end2)
//    {
//        temp[index++] = arr[begin2++];
//    }
//    for (int i = left; i <= right; i++)
//    {
//        arr[i] = temp[i];
//    }
//}
//
//void MergeSort(int* arr, int n)
//{
//    int* temp = (int*)malloc(sizeof(int) * n);
//    _MergeSort(arr, 0, n - 1, temp);
//    free(temp);
//    temp = NULL;
//}
//
//int singleNumber(int* nums, int numsSize)
//{
//    MergeSort(nums, numsSize);
//    for (int i = 0; i < numsSize; i++)
//    {
//        if ((nums[i] != nums[i - 1] && i - 1 >= 0) || (nums[i] != nums[i + 1] && i + 1 < numsSize))
//        {
//            return nums[i];
//        }
//    }
//    return -1;
//}
//
//int main()
//{
//    int arr[] = { 4,1,2,1,2 };
//
//    int ret = singleNumber(arr, 5);
//
//    return 0;
//}


//#include<stdio.h>
//#include<stdlib.h>
//
//void _MergeSort(int* arr, int left, int right, int* temp)
//{
//    if (left >= right)
//    {
//        return;
//    }
//    int mid = (left + right) / 2;
//    _MergeSort(arr, left, mid, temp);
//    _MergeSort(arr, mid + 1, right, temp);
//    int begin1 = left, end1 = mid;
//    int begin2 = mid + 1, end2 = right;
//    int index = left;
//    while (begin1 <= end1 && begin2 <= end2)
//    {
//        if (arr[begin1] < arr[begin2])
//        {
//            temp[index++] = arr[begin1++];
//        }
//        else
//        {
//            temp[index++] = arr[begin2++];
//        }
//    }
//    while (begin1 <= end1)
//    {
//        temp[index++] = arr[begin1++];
//    }
//    while (begin2 <= end2)
//    {
//        temp[index++] = arr[begin2++];
//    }
//    for (int i = left; i <= right; i++)
//    {
//        arr[i] = temp[i];
//    }
//}
//
//void MergeSort(int* arr, int n)
//{
//    int* temp = (int*)malloc(sizeof(int) * n);
//    _MergeSort(arr, 0, n - 1, temp);
//    free(temp);
//    temp = NULL;
//}
//
//int singleNumber(int* nums, int numsSize)
//{
//    MergeSort(nums, numsSize);
//    for (int i = 0; i < numsSize; i++)
//    {
//        if (nums[i] != nums[i + 1] && i + 1 < numsSize)
//        {
//            return nums[i];
//        }
//    }
//    return nums[numsSize - 1];
//}
//
//int main()
//{
//    int arr[] = { 1,2,1,3,2,5 };
//
//    int ret = singleNumber(arr, 6);
//
//    return 0;
//}


#include<stdlib.h>
#include<stdio.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void _MergeSort(int* arr, int left, int right, int* temp)
{
    if (left >= right)
    {
        return;
    }
    int mid = (left + right) / 2;
    _MergeSort(arr, left, mid, temp);
    _MergeSort(arr, mid + 1, right, temp);
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (arr[begin1] < arr[begin2])
        {
            temp[index++] = arr[begin1++];
        }
        else
        {
            temp[index++] = arr[begin2++];
        }
    }
    while (begin1 <= end1)
    {
        temp[index++] = arr[begin1++];
    }
    while (begin2 <= end2)
    {
        temp[index++] = arr[begin2++];
    }
    for (int i = left; i <= right; i++)
    {
        arr[i] = temp[i];
    }
}

void MergeSort(int* arr, int n)
{
    int* temp = (int*)malloc(sizeof(int) * n);
    _MergeSort(arr, 0, n - 1, temp);
    free(temp);
    temp = NULL;
}

int* singleNumber(int* nums, int numsSize, int* returnSize)
{
    MergeSort(nums, numsSize);
    int* RetArr = (int*)malloc(sizeof(int));
    int index = 0;
    for (int i = 1; i < numsSize - 1; i++)
    {
        if ((nums[i] != nums[i + 1] && i + 1 < numsSize) && (nums[i] != nums[i - 1] && i - 1 >= 0))
        {
            RetArr = (int*)realloc(RetArr, sizeof(int));
            RetArr[index++] = nums[i];
        }
    }
    if (nums[0] != nums[1])
    {
        RetArr = (int*)malloc(sizeof(int));
        RetArr[index++] = nums[0];
    }
    if (nums[numsSize - 1] != nums[numsSize - 2])
    {
        RetArr = (int*)malloc(sizeof(int));
        RetArr[index++] = nums[numsSize - 1];
    }
    *returnSize = index;
    return RetArr;
}

int main()
{
    int arr[] = { 1,2,1,3,2,5 };
    int i = 0;

    int* RetArr = singleNumber(arr, 6, &i);

    return 0;
}